package com.lun.swordtowardoffer2.c14;

import java.util.Arrays;

public class Rob {

	//方法一：带缓存的递归代码
	public int rob1(int[] nums) {
		if(nums.length == 0)
			return 0;
		
		int[] dp = new int[nums.length];
		
		Arrays.fill(dp, -1);
		helper(nums, nums.length - 1, dp);
		
		return dp[nums.length - 1];
	}
	
	private void helper(int[] nums, int i, int[] dp) {
		if(i == 0) {
			dp[i] = nums[0];
		}else if(i == 1) {
			dp[i] = Math.max(nums[0], nums[1]);
		}else if(dp[i] < 0){
			helper(nums, i - 2, dp);
			helper(nums, i - 1, dp);
			dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
		}
		
	}

	//方法二：空间复杂度为O(n)的迭代代码
	public int rob2(int[] nums) {
		if(nums.length == 0)
			return 0;
		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		if(nums.length > 1)
			dp[1] = Math.max(nums[0], nums[1]);
		
		for(int i = 2; i < nums.length; i++) {
			dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
		}
		
		return dp[nums.length - 1];
	}
	
	//方法三：空间复杂度为O(1)的迭代代码
	public int rob3(int[] nums) {
		if(nums.length == 0)
			return 0;
		
		int[] dp = new int[2];
		dp[0] = nums[0];
		if(nums.length > 1)
			dp[1] = Math.max(nums[0], nums[1]);
		
		for(int i = 2; i < nums.length; i++) {
			dp[i & 1] = Math.max(nums[i] + dp[(i - 2) & 1], dp[(i - 1) & 1]);
		}
		
		return dp[(nums.length - 1) & 1];
	}
	
	//方法四：用两个状态转移方程分析解决问题
	public int rob4(int[] nums) {
		if(nums.length == 0)
			return 0;
		
		int[][] dp = new int[2][2];
		
		dp[0][0] = 0;
		dp[1][0] = nums[0];
		
		for(int i = 1; i < nums.length; i++) {
			dp[0][i & 1] = Math.max(dp[0][(i - 1) & 1], dp[1][(i - 1) & 1]);
			dp[1][i & 1] = dp[0][(i - 1) & 1] + nums[i];
		}
		
		return Math.max(dp[0][(nums.length - 1) & 1], dp[1][(nums.length - 1) & 1]);
	}
	
}
